//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
//
// 
//
// 示例： 
//
// 输入：1->2->4, 1->3->4
//输出：1->1->2->3->4->4
// 
// Related Topics 链表 
// 👍 1250 👎 0

package leetcode.editor.cn;

import common.bean.ListNode;
import common.util.MyUtil;

/**
 * Java：合并两个有序链表
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P21_MergeTwoSortedLists {
    public static void main(String[] args) {
        Solution solution = new P21_MergeTwoSortedLists().new Solution();
        MyUtil.printListNode(solution.mergeTwoLists(MyUtil.createNode(1, 2, 4), MyUtil.createNode(1, 3, 4)));
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 递归
     */
    class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if(l1 == null) {
                return l2;
            }
            if(l2 == null) {
                return l1;
            }
            if(l1.val < l2.val) {
                l1.next = mergeTwoLists(l1.next, l2);
                return l1;
            } else {
                l2.next = mergeTwoLists(l1, l2.next);
                return l2;
            }
        }
    }
    ///**
    // * 迭代
    // */
    //class Solution {
    //    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    //        ListNode preHead = new ListNode(0);
    //        for (ListNode temp = preHead; l1 != null || l2 != null; temp = temp.next) {
    //            if (l1 == null) {
    //                temp.next = l2;
    //                break;
    //            } else if (l2 == null) {
    //                temp.next = l1;
    //                break;
    //            } else if (l1.val >= l2.val) {
    //                temp.next = l2;
    //                l2 = l2.next;
    //            } else {
    //                temp.next = l1;
    //                l1 = l1.next;
    //            }
    //        }
    //        return preHead.next;
    //    }
    //}
    //leetcode submit region end(Prohibit modification and deletion)

}